#include <bits/stdc++.h>

#define eb emplace_back
#define in read()
#define rep(i, x, y) for(int i = (x); i <= (y); i++)
#define per(i, x, y) for(int i = (x); i >= (y); i--)

using namespace std;

using vec = vector < int >;

int read() {
	int x = 0; bool f = 0; char ch = getchar();
	while(!isdigit(ch)) f |= ch == '-', ch = getchar();
	while(isdigit(ch)) x = x * 10 + (ch ^ 48), ch = getchar();
	return f ? -x : x;
}

const int N = 1e6 + 10;
const int inf = 0x3f3f3f3f;

int n, m, val[N], f[N][2], son[N], siz[N], ans;
vec G[N];

template < typename T > void chkmax(T &x, const T &y) { x = x > y ? x : y; }
template < typename T > void chkmin(T &x, const T &y) { x = x < y ? x : y; }

struct mat {
	int val[2][2];
	int* operator [](int x) { return val[x]; }
	const int * operator [](int x) const { return val[x]; }
	mat() { val[0][0] = val[0][1] = val[1][0] = val[1][1] = -inf; }
	friend mat operator * (mat a, mat b) {
		mat c;
		chkmax(c[0][0], a[0][0] + b[0][0]); chkmax(c[0][0], a[0][1] + b[1][0]);
		chkmax(c[0][1], a[0][0] + b[0][1]); chkmax(c[0][1], a[0][1] + b[1][1]);
		chkmax(c[1][0], a[1][0] + b[0][0]); chkmax(c[1][0], a[1][1] + b[1][0]);
		chkmax(c[1][1], a[1][0] + b[0][1]); chkmax(c[1][1], a[1][1] + b[1][1]);
		return c;
	}
} tval[N], sval[N];

int ch[N][2], fa[N], rt;
bool isrt[N];

void pu(int x) { sval[x] = sval[ch[x][0]] * tval[x] * sval[ch[x][1]]; }
void upd(int x) { tval[x][0][0] = tval[x][0][1] = f[x][0]; tval[x][1][0] = f[x][1]; tval[x][1][1] = -inf; }

void dfs(int x, int p) {
	fa[x] = p; siz[x] = 1; f[x][0] = 0; f[x][1] = val[x];
	for(auto y : G[x])
		if(y ^ p) dfs(y, x), siz[x] += siz[y], son[x] = siz[y] > siz[son[x]] ? y : son[x], f[x][0] += max(f[y][0], f[y][1]), f[x][1] += f[y][0];
}

void dfs1(int x, int p) {
	f[x][0] -= max(f[son[x]][0], f[son[x]][1]), f[x][1] -= f[son[x]][0]; upd(x);
	for(auto y : G[x]) if(y ^ p) dfs1(y, x); 
}

namespace bit {
	int stk[N], top;
	int build_chain(int l, int r) {
		if(l > r) return 0; int tot = 0, cur = 0; rep(i, l, r) tot += siz[stk[i]];
		rep(i, l, r) if((cur += siz[stk[i]]) * 2 >= tot)
			return pu(fa[ch[stk[i]][0] = build_chain(l, i - 1)] = fa[ch[stk[i]][1] = build_chain(i + 1, r)] = stk[i]), stk[i];
		return assert(0), 0;
	}
	int build(int x) {
		for(int y = x; y; y = son[y]) for(auto t : G[y]) if(t ^ son[y] && t ^ fa[y]) fa[build(t)] = y;
		top = 0; for(int y = x; y; y = son[y]) stk[++top] = y; return isrt[x = build_chain(1, top)] = true, x;
	}
	int lf[2], nf[2];
	void modify(int x, int y) {
		f[x][1] += y - val[x]; val[x] = y;
		while(x) {
			lf[0] = sval[x][0][0], lf[1] = sval[x][1][0];
			upd(x); pu(x);
			nf[0] = sval[x][0][0], nf[1] = sval[x][1][0];
			if(isrt[x]) {
				f[fa[x]][0] += max(nf[0], nf[1]) - max(lf[0], lf[1]); f[fa[x]][1] += nf[0] - lf[0];
			} x = fa[x];
		}
	}
}


int main() {
#ifndef ONLINE_JUDGE
	freopen("1.in", "r", stdin); freopen("P4751.out", "w", stdout);
#endif
	n = in, m = in; rep(i, 1, n) val[i] = in; rep(i, 2, n) { int u = in, v = in; G[u].eb(v); G[v].eb(u); }
	dfs(1, 0); dfs1(1, 0); 
	sval[0][0][0] = sval[0][1][1] = tval[0][0][0] = tval[0][1][1] = 0; fa[rt = bit :: build(1)] = 0;
	while(m--) {
		ans = 0; int x = in ^ ans, y = in;
		bit :: modify(x, y); printf("%d\n", ans = max({ sval[rt][0][0], sval[rt][0][1], sval[rt][1][0], sval[rt][1][1] }));
	}
	return 0;
}
